package easy;

/**
 * 面试题 17.16. 按摩师
 *
 * 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。
 * 在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。
 * 给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
 *
 * 注意：本题相对原题稍作改动
 *
 * 示例 1：
 * 输入： [1,2,3,1]
 * 输出： 4
 * 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
 *
 * 示例 2：
 * 输入： [2,7,9,3,1]
 * 输出： 12
 * 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
 *
 * 示例 3：
 *
 * 输入： [2,1,4,5,3,1,1,3]
 * 输出： 12
 * 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/the-masseuse-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class M17_16_按摩师 {
    public static void main(String[] args) {
        System.out.println(new M17_16_按摩师().massage(new int[]{2, 7, 9, 3, 1}));
    }

    /**
     * 假设第i个不接，则第i-1个可接可不接
     * dp[i][0] = max(dp[i-1][0],dp[i-1][1])
     *
     * 假设第i-1接，则第i一定接
     * dp[i][1] = dp[i-1][0] + numSi
     *
     * 最后答案为：
     * max(dp[n][0],dp[n][1]),n表示预约的个数
     *
     * 执行用时：0 ms, 击败了100.00%的用户
     * 内存消耗：35.9 MB, 击败了21.97%的用户
     */
    public int massage(int[] nums) {
        int n = nums.length;

        if (n==0) return 0;

        int dp00 = 0;
        int dp01 = nums[0];

        for (int i=1; i<n; i++){
            int dpt0 = Math.max(dp00, dp01);
            int dpt1 = dp00 + nums[i];

            dp00 = dpt0;
            dp01 = dpt1;
        }
        return Math.max(dp00, dp01);
    }
}
